1. Field of the Invention
The present invention relates to digital cellular communication systems, and more particularly, to a method and apparatus for the encryption of data communications within such a system.
2. History of the Prior Art
Cellular radio communications is, perhaps, the fastest growing field in the world-wide telecommunications industry. Although cellular radio communication systems comprise only a small fraction of the telecommunications systems presently in operation, it is widely believed that this fraction will steadily increase and will represent a major portion of the entire telecommunications market in the not too distant future. This belief is grounded in the inherent limitations of conventional telephone communications networks which rely primarily on wire technology to connect subscribers within the network. A standard household or office telephone, for example, is connected to a wall outlet, or phone jack, by a telephone cord of a certain maximum length. Similarly, wires connect the telephone outlet with a local switching office of the telephone company. A telephone user's movement is thus restricted not only by the length of the telephone cord, but also by the availability of an operative telephone outlet, i.e. an outlet which has been connected with the local switching office. Indeed, the genesis of cellular radio systems can be attributed, in large part, to the desire to overcome these restrictions and to afford the telephone user the freedom to move about or to travel away from his home or office without sacrificing his ability to communicate effectively with others. In a typical cellular radio system, the user, or the user's vehicle, carries a relatively small, wireless device which communicates with a base station and connects the user to other mobile stations in the system and to landline parties in the public switched telephone network (PSTN).
A significant disadvantage of existing cellular radio communication systems is the ease with which analog radio transmissions may be intercepted. In particular, some or all of the communications between the mobile station and the base station may be monitored, without authorization, simply by tuning an appropriate electronic receiver to the frequency or frequencies of the communications. Hence, anyone with access to such a receiver and an interest in eavesdropping can violate the privacy of the communications virtually at will and with total impunity. While there have been efforts to make electronic eavesdropping illegal, the clandestine nature of such activities generally means that most, if not all, instances of eavesdropping will go undetected and, therefore, unpunished and undeterred. The possibility that a competitor or a foe may decide to "tune in" to one's seemingly private telephone conversations has heretofore hindered the proliferation of cellular radio communication systems and, left unchecked, will continue to threaten the viability of such systems for businesses and government applications.
It has recently become clear that the cellular radio telecommunications systems of the future will be implemented using digital rather than analog technology. The switch to digital is dictated, primarily, by considerations relating to system speed and capacity. A single analog, or voice, radio frequency (RF) channel can accommodate four (4) to six (6) digital, or data, RF channels. Thus, by digitizing speech prior to transmission over the voice channel, the channel capacity and, consequently the overall system capacity, may be increased dramatically without increasing the bandwidth of the voice channel. As a corollary, the system is able to handle a substantially greater number of mobile stations at a significantly lower cost.
Although the switch from analog to digital cellular radio systems ameliorates somewhat the likelihood of breeches in the security of communications between the base station and the mobile station, the risk of electronic eavesdropping is far from eliminated. A digital receiver may be constructed which is capable of decoding the digital signals and generating the original speech. The hardware may be more complicated and the undertaking more expensive than in the case of analog transmission, but the possibility persists that highly personal or sensitive conversations in a digital cellular radio system may be monitored by a third party and potentially used to the detriment of the system users. Moreover, the very possibility of third parties eavesdropping of a telephone conversation eliminates cellular telecommunications as a medium for certain government communications. Certain business users may be equally sensitive to even the possibility of a security breech. Thus, to render cellular systems as viable alternatives to the conventional wireline networks, security of communications must be available on at least some circuits.
Various solutions have been proposed to alleviate the security concerns engendered by radio transmission of confidential data. A known solution, implemented by some existing communication systems, uses cryptoalgorithms to encrypt (scramble) digital data into an unintelligible form prior to transmission. For example, the article entitled "Cloak and Data" by Rick Grehan in BYTE Magazine, dated June 1990 at pages 311-324, for a general discussion of cryptographic systems. In most systems currently available, speech is digitized and processed through an encryption device to produce a communications signal that appears to be random or pseudo-random in nature until it is decrypted at an authorized receiver. The particular algorithm used by the encryption device may be a proprietary algorithm or an algorithm found in the public domain. Further background for such techniques may be found in the article entitled "The Mathematics of Public-Key Cryptography" by Martin E. Hellman in Scientific American dated August 1979 at 146-167.
In 1977, the U.S. National Bureau of Standards published a cryptoalgorithm defined as the Data Encryption Standard (DES). See Federal Information Processing Standards Publication 46 (FIPS PUB 46) of the National Technical Information Service (1977). The DES method of encryption utilizes a publicly known mathematical algorithm, which produces a stream of random numbers, and a data encryption key consisting of a 64 bit binary word. Digital data, typically in ASCII format, is transformed into an apparently random sequence of bits. The encrypted data can be decrypted pursuant to the standard DES decryption procedure only if the encryption key, which may be any 64 bit binary word, is also known to the receiver of the encrypted data. Because the DES encryption and decryption procedures are publicly known, the security of the key is crucial to the effective use of DES.
Commercial devices implementing the DES encryption/decryption procedure are generally in the form of integrated circuits which accept as a first input the data to be encrypted and as a second input the 64 bit key. Most such devices operate in a cipher feedback (CFB) mode in which the encrypted data is provided as a third input to the DES device so as to prevent the transmission of repetitive sequences of encrypted data when the data being encrypted contains repetitive sequences of identical characters. The chief advantage of CFB encryption of data is self synchronization of the encrypted signal. However, a major disadvantage of CFB devices operating over an RF link is the reduced operational range of the mobile stations caused by error multiplication related to receiver sensitivity. That is, a single error in Transmission of an encrypted data block produces, on average, half of the bits in the deciphered data to be in error producing a hugh magnification of the transmission error rate. Thus, a mobile station would have to remain within a certain limited range of a base station in order to maintain a sufficiently high signal-to-noise ratio to attempt to avoid erroneous reception of transmitted data bits. Error multiplication occurs in CFB mode because erroneously received bits are continuously fed back to the decryption device until the error propagates out and the receiver eventually resynchronizes.
Another known technique for the encryption of data, which does not suffer from the error multiplication problem encountered in the CFB mode of operation, is counter addressing (CA). In the CA mode of operation, a keystream generator is used to produce a pseudo-random keystream of bits by processing an encryption key containing a plurality of key data bits. The keystream is then used by the encryption device to encrypt the data signal. Typically, the keystream is added (modulo-2) with the data signal on a bit-by-bit basis by an exclusive OR (XOR) logic gate to produce a scrambled binary data signal. The scrambled signal may be descrambled by adding (modulo 2) to the scrambled signal an identical keystream generated synchronously by an identical keystream generator that is initialized with the same binary encryption key. In this fashion, the encryption device may be "addressed" by the pseudo-random counter. Thus, in CA mode, continuous bit synchronization between the scrambler to the descrambler is required in order to allow proper operation of the descrambler key generator without necessitating periodic key generator data transfers. Unfortunately, bit synchronization over an RF channel in a cellular radio system is very difficult to maintain due, in large part, to the phenomena of Rayleigh fading which is caused by the movement of the mobile station through the multi-path interference patterns generated by reflection from obstacles near the receiving equipment. A single error bit in transmission through the decryption circuit out of phase with the encryption circuit and the output produced at the receiver is meaningless. The CA technique is generally unsuitable for radio link encryption which must be more robust against bit transmission errors.
The difficulties attending continuous bit synchronization have led to the use of "time-of-day" or "frame number" driven keystream generators. Such keystream generators may be synchronized to a time of day counter, i.e. hour, minute and second, or to a simple number counter and the encryption and decryption circuits can be sending the current count in the event one falls out of synchronization with another.
To increase the security of communications in systems utilizing time-of-day or frame number driven keystream generators, the value of each bit in the pseudo-random keystream is preferably made a function of the values of all the key bits in the encryption key. In this manner, a person desiring to descramble the encrypted signal must "crack" or "break" all of the bits of the encryption key which may be in the order of a hundred (100) bits or more. A keystream of this type is generally produced by mathematically expanding the encryption key word in accordance with a selected algorithm which incorporates the count of the time-of-day counter. However, if every bit of the encryption key is to influence every bit in the keystream and if the keystream is to be added to the data stream bits on a one-to-one basis, the required number of key word expansion computations per second is enormous and can readily exceed the real time computational capability of the system. While the degree of necessary computations suggests the use of a supercomputer, the cost of supercomputers for this purpose is prohibitive. Therefore, a method and apparatus are needed to achieve the expansion of the keystream with conventional microprocessors and at conventional microprocessor speeds.